package pri.zjy.backTracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author zhangjy
 * @description 组合总和 II
 * <p>
 * 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的每个数字在每个组合中只能使用 一次 。
 * <p>
 * 注意：解集不能包含重复的组合。
 * @date 2025/6/13 14:19
 */
public class CombinationSum2_40 {

    public static void main(String[] args) {

        CombinationSum2_40 combinationSum240 = new CombinationSum2_40();

        int[] candidates = {2, 5, 2, 1, 2};
        int target = 5;

        combinationSum240.combinationSum(candidates, target).forEach(System.out::println);

    }

    /**
     * 参考dmsxl
     * <p>
     * 思路：虽然每个元素只能用一次，但是元素是可重复的（组合、组合总和、组合总和 III都是元素不重复）；所以要在搜索过程中进行去重
     * <p>
     * 分析：由题目可知，目标元素是可重复的，但是每个元素只能用一次
     */
    List<List<Integer>> ans2 = new ArrayList<>();

    List<Integer> path2 = new ArrayList<>();

    boolean[] used2;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used2 = new boolean[candidates.length];
        // 加标志数组，用来辅助判断同层节点是否已经遍历
        Arrays.fill(used2, false);
        // 为了将重复的数字都放到一起，所以先进行排序
        Arrays.sort(candidates);
        backtrack2(candidates, target, 0);

        return ans2;
    }

    public void backtrack2(int[] candidates, int target, int startIndex) {
        // target减为0，则记录目标组合
        if (target == 0) {
            ans2.add(new ArrayList<>(path));
            return;
        }
        // target<0，直接结束本层递归
        if (target < 0) {
            return;
        }

        // 横向遍历
        for (int i = startIndex; i < candidates.length; i++) {
            // 出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
            // 为什么是!used2[i - 1]？——要求在同一个树的层级中，前一个元素没使用过，才会跳过。
            if (i > 0 && candidates[i] == candidates[i - 1] && !used2[i - 1]) continue;

            // 记录元素
            path2.add(candidates[i]);
            used2[i] = true;

            // 向下递归
            // 下层从 i+1 开始，避免重复使用同一个元素
            // 下层要找的target为target - candidates[i]；是隐藏回溯，不用显示回溯target
            backtrack2(candidates, target - candidates[i], i + 1);

            // 回溯
            path2.remove(path2.size() - 1);
            used2[i] = false;
        }
    }

    /**
     * 个解：回溯（错误！！！）
     * <p>
     * 错误原因：未对最后结果去重；需要在搜索过程中进行组合的去重
     */
    List<List<Integer>> ans = new ArrayList<>();

    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtrack(candidates, target, 0);

        return ans;
    }

    public void backtrack(int[] candidates, int target, int startIndex) {
        // target减为0，则记录目标组合
        if (target == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        // target<0，直接结束本层递归
        if (target < 0) {
            return;
        }

        // 横向遍历
        for (int i = startIndex; i < candidates.length; i++) {
            // 记录元素
            path.add(candidates[i]);

            // 向下递归
            // 下层从 i+1 开始，避免重复使用同一个元素
            // 下层要找的target为target - candidates[i]；是隐藏回溯，不用显示回溯target
            backtrack(candidates, target - candidates[i], i + 1);

            // 回溯
            path.remove(path.size() - 1);
        }
    }

}
